package simplifiedFractions

import "strconv"

/*
找出分母最大为n，分子小于n的，最简分数
*/
func simplifiedFractions(n int) []string {
	ans := []string{}
	for i := 1; i <= n; i++ {
		for j := 1; j < i; j++ {
			if check(i, j) {
				ans = append(ans, strconv.Itoa(j)+"/"+strconv.Itoa(i))
			}
		}
	}
	return ans
}

// 判断是否存在公因数，辗转相除
func check(i, j int) bool {
	if j == 1 {
		return true
	}
	r := i % j
	for r != 1 {
		// 此时的公因数为j
		if r == 0 {
			return false
		}
		if j == 1 {
			return false
		}
		i, j = j, r
		r = i % j
	}
	return true
}
